import java.util.*;

class Solution21 {
    public int[][] insert(int[][] intervals, int[] newInterval) {
        int left = 0;
        int right = intervals.length;
        int mid;
        //找到与新加区间有重叠的第一个区间的前一个区间start
        while(right > left) {
            mid = left + (right - left) / 2;
            if(intervals[mid][1] < newInterval[0] ) {
                left = mid + 1;
            }else {
                right = mid;
            }
        }
        int start = left - 1;
        left = 0;
        right = intervals.length;
        //找到与新区间有重叠的最后一个区间后一个区间end
        while(right > left) {
            mid = left + (right - left) / 2;
            if(intervals[mid][0] > newInterval[1]) {
                right = mid;
            }else {
                left = mid + 1;
            }
        }
        int end = left;
        int[][] result = new int[start + 2 + intervals.length - end][2];
        for(int i = 0; i <= start; i++) {
            result[i] = intervals[i];
        }
        for(int i = end; i < intervals.length; i++) {
            result[start + i - end + 2] = intervals[i];
        }
        int[] tmp = new int[2];
        tmp[0] = Math.min(newInterval[0], start + 1 < intervals.length ? intervals[start + 1][0] : newInterval[0]);
        tmp[1] = Math.max(newInterval[1], end - 1 >= 0 ? intervals[end - 1][1] : newInterval[1]);
        result[start + 1] = tmp;

        return result;
    }
}